package main

import "fmt"

/*
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

作者：宫水三叶
链接：https://leetcode-cn.com/leetbook/read/path-problems-in-dynamic-programming/rt1hg6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	var dp [][]int
	for i := 0; i < len(obstacleGrid); i++ {
		dp = append(dp, make([]int, len(obstacleGrid[i])))
	}
	// base case，注意base case区别于uniquePaths的内容
	for i := 0; i < len(obstacleGrid); i++ {
		if obstacleGrid[i][0] == 1 {
			dp[i][0] = 0
			break // 因为只能往下和往右，所以第一行，如果左侧一个位置出现阻断，则它右侧的位置都是不可达的，所以break即可
		}
		dp[i][0] = 1
	}
	for j := 0; j < len(obstacleGrid[0]); j++ {
		if obstacleGrid[0][j] == 1 {
			dp[0][j] = 0
			break // 因为只能往下和往右，所以第一行，如果上面一个位置出现阻断，则它下面的位置都是不可达的，所以break即可
		}
		dp[0][j] = 1
	}
	// 状态转移
	for i := 1; i < len(dp); i++ {
		for j := 1; j < len(dp[i]); j++ {
			// 如果中间有阻断，也是置为0
			if obstacleGrid[i][j] == 1 {
				dp[i][j] = 0
				continue
			}
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	// for i := 0; i < len(dp); i++ {
	// 	fmt.Println(dp[i])
	// }
	return dp[len(dp)-1][len(dp[0])-1]
}

func main() {
	obstacleGrid := [][]int{{0, 0}, {1, 1}, {0, 0}}
	fmt.Println(uniquePathsWithObstacles(obstacleGrid))

}
